package com.xzz.tree;

/**
 * @author: hhz
 * @create: 2021-12-17 15:22
 * 给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：
 *
 * 二叉树的根是数组 nums 中的最大元素。
 * 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
 * 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
 * 返回有给定数组 nums 构建的 最大二叉树 。
 **/
public class ConstructMaximumBinaryTree {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{3,2,1,6,0,5};
        TreeNode treeNode = constructMaximumBinaryTree(nums);
        preTraverse(treeNode);

    }
    public static TreeNode constructMaximumBinaryTree(int[] nums) {
       return  constructMaximumBinaryTreeBuild(nums,0,nums.length-1);
    }
    public static void preTraverse(TreeNode treeNode){
        if(treeNode!=null){
            System.out.print(treeNode.val+" ");
            preTraverse(treeNode.left);
            preTraverse(treeNode.right);
        }
    }
    public static TreeNode constructMaximumBinaryTreeBuild(int[] nums,int start,int end){
        if(start > end ){
            return null;
        }
        //注意这个最小值
        int max= Integer.MIN_VALUE;
        int index = -1;
        for (int i = start; i <= end; i++) {
            if(nums[i]>max){
                max = nums[i];
                index = i;
            }
        }
        TreeNode node = new TreeNode(max);
        node.left = constructMaximumBinaryTreeBuild(nums,start,index-1);
        node.right = constructMaximumBinaryTreeBuild(nums,index+1,end);
        return node;
    }
}
